package codingforgreat.class42;

public class Class01_Lc265_PrintII {
    //贪心解：记录i - 1 的最优解与次优解，向下遍历即可
    //长度为N的数组 int【i】【j】表示第i个各自涂上第j种颜色的花销
    public static int print(int[][] costs){
        int N = costs.length;
        int K = costs[0].length;
        if(N == 0){
            return 0;
        }
        int preMin1 = -1;
        int preEnd1 = -1;

        int preMin2 = -1;
        int preEnd2 = -1;

        for (int i = 0; i < N; i++) {
            int curMin1 = Integer.MAX_VALUE;
            int curEnd1 = -1;
            int curMin2 = Integer.MAX_VALUE;
            int curEnd2 = -1;
            for(int j = 0; j < K; j++){
                if (j != preEnd1) {
                    if (preMin1 + costs[i][j] < curMin1) {
                        curMin2 = curMin1;
                        curEnd2 = curEnd1;
                        curMin1 = preMin1 + costs[i][j];
                        curEnd1 = j;
                    } else if (preMin1 + costs[i][j] < curMin2) {
                        curMin2 = preMin1 + costs[i][j];
                        curEnd2 = j;
                    }
                } else if (j != preEnd2) {
                    if (preMin2 + costs[i][j] < curMin1) {
                        curMin2 = curMin1;
                        curEnd2 = curEnd1;
                        curMin1 = preMin2 + costs[i][j];
                        curEnd1 = j;
                    } else if (preMin2 + costs[i][j] < curMin2) {
                        curMin2 = preMin2 + costs[i][j];
                        curEnd2 = j;
                    }
                }
            }
            preMin1 = curMin1;
            preEnd1 = curEnd1;
            preMin2 = curMin2;
            preEnd2 = curEnd2;
        }
     return preMin1;

    }

}
